\section{Host Identity Protocol}
In this section we give a brief overview of the Host Identity Protocol,
which we use as building block in the thesis. The HIP architecture is
defined in \cite{hip_arch}, and the Internet draft of the protocol is defined in \cite{hip_draft}. 
There are also other IETF documents about HIP like mobility and multihoming
\cite{hip_mm}, NAT traversal issues \cite{hip_nat}, HIP IPsec handling
\cite{hip_ipsec} and DNS related issues \cite{hip_dns}. 
Descriptions given here are not supposed to summarize all these Internet
drafts and publications, but try to explain why we use HIP as building
block.
\subsection{Dual Role of IP and its Restrictions}
As in the 1970s, when TCP/IP was designed, computers  were large, stationary
and bound to wired power lines. The interconnection of computers
depended  on wired cables. The locator, in the TCP/IP protocol
suite the IP address, played a dual role: they were used as location
information for packets routing, and as identifier of the host. The dual
role had worked fine as long as the computers were stationary, but it quickly
showed its disadvantages.

Already in the early 1990s, when the Internet was spreading using telephone
lines and modems, there was already a problem with the IP addressing scheme.
Every time
a user gets a new IP address when dialing into the Internet. Thus the
Internet Service Providers (ISP) must log the activities of the user to
show exactly when a user gets an IP address using what telephone number.

The problems were getting worse when notebook computers began to dominate
the market and wireless networks were spreading. Other handheld devices like
smart phones, PDAs are also able to go to the Internet using wireless technologies. Nomadic users change
their locations and get  new IP addresses assigned, in a wired or wireless network.
The IP address is overstrained in its dual role. Furthermore, because the
connections are bound to $<$\texttt{ip, port}$>$, the transport 
connections break every time when a
new IP address is assigned. Macro mobility as defined in section
\ref{sec:mobility_def} is not possible. 

\subsection{A new Namespace in HIP}
The Host Identity Protocol (HIP) architecture \cite{hip_arch} is designed 
to decouple the dual role of 
the IP address. It introduces a new namespace, the \emph{Host
Identity} (HI) namespace, 
which is located between the IP layer and the transport layer (see Figure
\ref{img:hip_arch}). The HI is used to represent the identity of
a host. A host can have one or more Host Identities, for example one for
normal use, and one for anonymous use, or if multiple users are sharing the
same host, each Host Identifier can represent a user. The IP layer 
is only responsible for IP packet routing and  transmission.
\begin{figure}[htb]
 \centering
 \includegraphics[width = 13cm]{pics/hip}
 \caption{The new namespace under HIP}
 \label{img:hip_arch}
\end{figure}

In HIP, the host identifiers are public keys. Each public key is associated
with a private key which can be used to proof the legitimization
of the host identity. Typically a public key has the size of at least 1024
bits, which is too big to be used as an identifier directly. Therefore, a
\textbf{Host
Identity Tag (HIT)} of 128 bits is used to represent the host identity. A
HIT is gained by applying a cryptographic hash function to the public key.

Using HIT of constant size instead of HI has several advantages. Firstly,
due to its size, a HIT can be directly used in an IP datagram. Secondly,  
a HIT has the same size as an IPv6 address, which makes the
integration of HIP in the current Internet infrastructure and the
interoperability with legacy API easier. Thirdly,
the constant size of the HIT makes also a standard API easier.

The HIT is self-certificating, i.e. only a peer who is in possession of the
private key can use the HIT as identifier.
\subsection{Protocol Overview}
The Host Identity Protocol consists of three main parts. Firstly, the \emph{Base Exchange}
is used to authenticate the two communicating peers and to establish IPsec
security associations for each direction using the classic Diffie-Hellmann
key exchange procedure \cite{rfc2631}. Secondly, after a successful Base
Exchange, an \emph{ESP tunnel} is established which is used to 
carry the datagrams securely between the two peers. Additionally, HIP 
provides a mechanism to support
\emph{Mobility and Multihoming}. The mobility refers to the \emph{Macro
Mobility} as defined in section \ref{sec:mobility_def}. If a host has more
than one network interfaces and each of the interfaces is reachable under a
different IP address, we call it \emph{Multihoming}. In the following section, we give a brief
introduction of the each part.
\subsection{The Base Exchange}\label{sec:bex}

The Base Exchange (BEX) in HIP,  a four way 
handshake protocol, is the main building block of the Host Identity
Protocol. It is used mainly for mutual authentication and for the establishment of
a pair of IPsec security associations between the two communicating peers.
Diffie-Hellman key exchange protocol is used to create shared secrets.
Because the HITs are self-certificating, no certificates are required.

Since we will extend and modify the Base Exchange for authentication in our
thesis, we  give a short presentation of the Base Exchange and the
usage of each packet. Figure \ref{img:bex} gives an overview of the
Base Exchange.
\begin{figure}[htb]
 \centering
 \includegraphics[width = 14cm]{pics/BEX}
 \caption{Overview of the HIP Base Exchange}
 \label{img:bex}
\end{figure}

During the Base Exchange, the host that starts the BEX is called
\emph{Initiator} and the other peer is called \emph{Responder}. These roles
disappear after the Base Exchange is accomplished.

\subsubsection{The First Initiator Packet (I1)}
The Base Exchange is triggered by the Initiator sending the \emph{first
initiator packet} (I1). The I1 packet contains nothing more than the HIT of
its own and the HIT of the Responder, if it is known. This is designed to
prevent DoS-attacks that aim at consuming the CPU-power and memory of the 
Responder, because the I1 packet is not authenticated and can be used by an
attacker to start an I1-flood.
Every HIP control packet must
contain the Initiator's HIT (HIT-I) and the Responder's HIT (HIT-R).
\subsubsection{The First Responder Packet (R1)}
The reception of the I1 packet triggers the \emph{first responder packet} 
(R1). With the R1, the
Diffie-Hellmann key exchange starts. 

The Responder can reuse the pre-created
partial R1 packet, in this way the Responder can 
reply the I1 rapidly. Additionally, DoS-attacks can be prevented by using
the pre-created partial R1 packet, because the Responder does not need to
sign the packet before sending it. 

The pre-computed partial packet includes its own HIT,
the Diffie-Hellman public key, the encryption algorithms which are
supported by the Responder (known as \emph{HIP transforms}), the ESP
transforms.
The partial packet is signed and saved so
that a complete R1 packet can be constructed quickly.

It is important that at this moment, no protocol state should be created in
order to prevent DoS-attacks.

On receiving the I1 packet, the Responder 
inserts contents into the pre-created packets which must be different in
every packet. These include 
the HIT of the Initiator, a puzzle and an \emph{echo request} parameter.
The puzzle must be solved by the Initiator and  is designed in a
way that creating a puzzle is easier than solving it. The difficulty of
the puzzle can be adjusted by the Responder based on factors like trust
level, load balance etc. The puzzle is designed to prevent or slow
down some kinds of DoS-attacks, so that the attackers must spend
considerable CPU time to get a protocol state established. The difficulty
here affects the CPU time the
Initiator must spend to solve the puzzle. It can be set to zero if the
Initiator is fully trusted and no DoS-attacks are suspected.
The HIT-R and the puzzle are not protected by the signature.

The \emph{echo-request} parameter has only meaning to the Responder and
should be echoed back without modification by the Initiator in the next
packet. This property can be used by the Responder to delay the state
establishment, for example as identifier to demultiplex the traffic. 

However, the \emph{puzzle} and the \emph{echo-request} are not protected by the signature
which only covers the partial packet. An attacker can intercept the packet
and manipulate the puzzle, for example to increase the difficulty of the
puzzle. In this way, a DoS attack against the Initiator is possible. To
solve the problem, an \emph{R1-counter} parameter is used to keep the
freshness of the R1 packet.
\subsubsection{The Second Initiator Packet (I2)}
On receiving the R1 packet, the Initiator firstly checks the state whether
a corresponding I1 packet was already sent. Then it verifies the signature
of the R1 packet. The puzzle will only be solved if the signature is valid,
otherwise the danger exists that the Responder is not authentic and it
must waste time to solve the puzzle. Then the \emph{second initiator
packet} I2 packet is created which
contains the following contents:

The solution of the puzzle is included in the I2 packet. The Initiator
calculates its Diffie-Hellman public key, from
now on, the Initiator knows the shared secret and derives the session key 
from it 
for the Base Exchange. He selects one of the HIP-transforms
and the ESP transforms which are proposed by the Responder. The Host
Identity (public key) can be optional encrypted using the session key 
and the selected
algorithm. The \emph{echo-request} from  R1 is echoed back 
without any modification
in the packet. A security parameter index (SPI) for the
Responder-to-Initiator SA is also created and included in the I2 packet.

The I2 packet is also protected by an HMAC signature. The HMAC, the
\emph{keyed-Hash Message Authentication Code} \cite{hmac} is calculated by a hash
function together with a secret. The HMAC is inexpensive in terms of CPU
cycle but it can help the Responder against attacks using bogus DH key
and bogus signature.

Without the HMAC signature, an attacker can forge an I2 packet with bogus
DH key and bogus RSA/DSA signatures. Since  the verification of the signature are expensive in terms of CPU cycle,
an attacker can use this kind of attack to let the Responder consume its 
CPU power. But with HMAC, the Responder can save the signature verification
by proofing the HMAC signature at first. 

Additionally,
an RSA/DSA signature covers the entire packet and then the packet is sent to the
Responder.
\subsubsection{The Second Responder Packet (R2)}
On receiving the I2 packet, the Responder firstly checks the solution of the
puzzle, because checking the solution of the puzzle is easier than solving
it. If the solution is correct, the Responder will be sure that the
Initiator has spend considerable CPU time to establish a state. It then  
calculates the session
key and uses the session key to decrypt the Host Identity of the
Initiator, if it is encrypted. It uses the Host ID to verify the packet 
signature. After
that, the \emph{second responder packet} (R2) packet is created. The R2 includes a SPI for the
Initiator-to-Responder Security Association, a HMAC signature and a RSA/DSA
signature for the packet. The R2 packet is then sent to the Initiator.
\subsection{Result of Base Exchange}
For the Initiator, on receiving the R2 packet, it will verify the HMAC
signature and the RSA/DSA signature. The validation of the HMAC signature
implies that the Responder has also the right session key. Since 
security
associations are created for both inbound and outbound traffic, a secure
ESP tunnel exists
between the two peers which can be
used to transfer data securely. IPsec and  ESP will be introduced in more
detail in section \ref{sec:ipsec}.

\subsection{Closing a HIP Association}
If a HIP association is not needed, it can be closed. However, the close
procedure must be protected from DoS-attacks, i.e., only the peers in an
HIP association are authorized to close it.

The host that is going to close a HIP association sends a \emph{Close} 
packet to
the peer, which should be replied by a \emph{Close Ack} packet. 

In the \emph{Close}
packet, an \emph{echo request signed} parameter is included, and the 
entire \emph{Close} packet
is protected by a HMAC signature and a RSA/DSA signature. 

On receiving the \emph{Close} packet, the peer must firstly check whether a HIP
state is available and then verify the HMAC and the
RSA/DSA signatures. The validation of the HMAC signature means that the
host which have sent the \emph{Close} packet knows the session key and RSA/DSA
signature proves that the packet is really from the peer represented by the
HIT. Then it creates the \emph{Close Ack} packet which contains a
\emph{echo response signed} parameter. The entire packet is protected by a
HMAC-signature and a RSA/DSA signature.

On receiving the \emph{Close Ack} packet, the host checks whether the
\emph{echo request}
is responded and verifies the HMAC and the
RSA/DSA signature. If they are valid, the host can close the HIP
association and delete the HIP state.
\subsection{Mobility and Multihoming}
Since in HIP the applications are bound to $<$\texttt{HIT, port}$>$ and 
the  IP addresses are 
only used for routing, the mobile client can change his IP address
and continue to communicate with the peer using HIT, provided that both
peers update their mapping between HITs and IP addresses.
In this section, we firstly discuss the HIP Update process. Multihoming is
introduced in section \ref{sec:multihoming}.

The HIP update process is defined in the HIP mobility and multihoming draft \cite{hip_mm}.
The new IP addresses are included in the  \emph{locator} parameter. 
In the following
subsections, we briefly illustrate the Update process for mobility using the
\emph{locator} parameter. The Update process is accomplished within 3 HIP control
packets, we describe the content and processing of the each packet.

The overview of the Update process is depicted in Figure \ref{img:mobility}.
\begin{figure}[htb]
 \centering
 \includegraphics[width = 13cm]{pics/mobility}
 \caption{The HIP mobility process}
 \label{img:mobility}
\end{figure}

%The UPDATE process consists of three Update-messages:
\subsubsection{The First Update Packet}
We assume that the mobile user moves from one access point to
another and gets a new IP address that is different from the old
one. 
On getting the new IP address, the mobile client sends the first
Update packet to inform its peer about its new point of network attachment.

The \emph{locator} parameter in the first Update packets contains the new IP
address information. In addition to the new IP address, the Update packet
also includes an \emph{esp-info} parameter with SPI information 
for the parameter
inspecting middleboxes. Also a \emph{seq} parameter is included in the first
Update packet to prevent replay attack. The packet is protected by both a
HMAC and a RSA/DSA signature.
\subsubsection{The Second Update Packet}
On receiving the first Update packet, the stationary peer firstly checks the
HMAC signature. Since the session key is known only by the two communicating
peers, it suffices only to check the HMAC signature. The verification of the
RSA/DSA signature can be escaped. But the RSA/DSA signature may be needed
by the middleboxes to verify the identity of the peers.

If the signatures are valid, the stationary host updates the mapping
between HIT and the IP address and packs the \emph{esp-info}
parameter into the packet, together with the \emph{seq} parameter to prevent
replay attack. It also appends an \emph{ack} parameter which acknowledges the
previous packet. At this moment, it is still not sure whether the new destination
address is valid, so the new IP address must be verified. For this purpose,
an \emph{echo-request} parameter is appended into the packet, which 
should be
responded unmodified back in the next packet. The packet is protected by a
HMAC and a DSA/RSA signature.

\subsubsection{The Third Update Packet}
On receiving the second Update packet, the mobile client firstly checks the
signature. If it is  valid, he acknowledges the packet using an \emph{ack}
parameter and responses the \emph{echo-request} parameter by using 
an \emph{echo-response}
parameter. The whole packet is signed by a HMAC and DSA/RSA signature and
then sent back to the peer.

On receiving the Update packet containing the \emph{echo response} parameter, the
stationary peer is fully convinced that the new IP address is valid and the
data transfer can continue in the new ESP tunnel.

\subsubsection{Multihoming} \label{sec:multihoming}
Contrary to mobility, where different IP addresses are used sequentially,
in multihoming, there are simultaneously more than one IP addresses under
which the host
can be reached. For multihoming, all IP addresses are packed in the
\emph{locator} parameter and one particular IP address is declared as
\emph{preferred address}.
\subsection{HIP Control Packet Formats}
HIP uses control packets to establish, update, or close a HIP
association. All control packets have the same common packet format which is
displayed in Figure \ref{img:hip_control}. We give a
brief description to the format of the HIP header, the description is
based on the HIP base draft \cite{hip_draft}.
\begin{figure}[htb]
 \centering
 \includegraphics[width = 13cm]{pics/control_packet}
 \caption{The structure of HIP header}
 \label{img:hip_control}
\end{figure}
The HIP base draft defines the \emph{Next Header} only as decimal number
59, which means  no further headers are supported by the HIP
control packets. 
The \emph{packet type} indicates the type of the packet. The types can be
\emph{Update},
\emph{Close} or packets in Base Exchange. How a packet is processed depends on the
type of the packet.

The control bits in the HIP header are used to indicate 
the capability of the host. Currently the base draft only defines one
control bit, the \emph{A}-bit. A  stands for \emph{Anonymous}, if this bit is set, it means that the
sender's HI in the packet is anonymous.
\emph{Sender's and Receiver's HIT}
are always 128-bit long.
\subsubsection{HIP Parameters}\label{sec:hip_parameters}
The header length, packet type etc. mentioned above are mandatory for 
every packet. The appearance of other information 
like the Host ID, Diffie-Hellman public key, puzzle, solution, signature 
etc. as described in section \ref{sec:bex} depends on the type of the
packet and may have a variable length. We call this kind of information
\emph{HIP Parameter}.

The HIP base draft defines a unified format, the \emph{Type Length Value}
(TLV) format for HIP parameters. The basic structure of the TLV format is depicted in Figure
\ref{img:tlv}. We describe the structure briefly as follows:
\begin{figure}[htb]
 \centering
 \includegraphics[width = 13cm]{pics/hip_parameter}
 \caption{The structure of HIP Parameter}
 \label{img:tlv}
\end{figure}
The \emph{Type} of the parameter takes 16 bits, the C-bit (Critical bit) is part of the type.
It is the least significant bit of the parameter type. If the
C-bit is set, then the parameter is \emph{critical} and must be implemented
by the recipient. All critical parameters have  odd type numbers, and
non-critical parameters have even type numbers.
The \emph{Contents} are the actual transferred data like Host ID or puzzle.
The \emph{Padding} is used to make the total length of the parameter 
to be a multiple of 8 bytes. The padding can have a length between 0 to 7
bytes. This is used for data alignment.

When parameters are included in the HIP header, care must be taken about the
order of different parameters. According to the HIP base draft, the ordering
of the parameters is strictly enforced to be ascending \cite{hip_draft}. 
